package oj;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;

/**
 * @author 郝文雪
 * @date 2022/9/11 0:01
 * @Description Test
 */
public class LC85 {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0) return 0;
        int maxArea=0;
        int[] heights=new int[matrix[0].length];
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]=='1'){
                    heights[j]+=1;
                }else{
                    heights[j]=0;
                }
            }
            maxArea=Math.max(maxArea,max(heights));
        }
        return maxArea;
    }
    private int max(int[] heights){
        int maxArea=0;
        Deque<Integer> d=new ArrayDeque<>();
        int p=0;
        while(p<heights.length){
            if(d.isEmpty()){
                d.addLast(p);
                p++;
            }else{
                if(heights[p]>=heights[d.peekLast()]){
                    d.addLast(p);
                    p++;
                }else{
                    int cur=heights[d.pollLast()];
                    int left=d.isEmpty()?-1:d.peekLast();
                    int right=p;
                    int area=(right-left-1)*cur;
                    maxArea=Math.max(area,maxArea);
                }
            }
        }
        while(!d.isEmpty()){
            int cur=heights[d.pollLast()];
            int left=d.isEmpty()?-1:d.peekLast();
            int right=heights.length;
            int area=(right-left-1)*cur;
            maxArea=Math.max(area,maxArea);
        }
        return maxArea;
    }
}
